TNotes.leetcode

Appearance

0119. 杨辉三角 II【简单】

0119. 杨辉三角 II【简单】 ​

1. 📝 题目描述 ​

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例 1：

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2：

输入: rowIndex = 0
输出: [1]

示例 3：

输入: rowIndex = 1
输出: [1,1]

提示：

  • 0 <= rowIndex <= 33

进阶：

你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

2. 🎯 s.1 - 暴力解法 ​

svg

js
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
  if (rowIndex === 0) return [1]
  if (rowIndex === 1) return [1, 1]

  // 初始化
  const triangle = []
  for (let i = 0; i <= rowIndex; i++) triangle.push(new Array(i + 1).fill(1))

  // 内层求和
  for (let r = 2; r <= rowIndex; r++)
    for (let c = 1; c <= r - 1; c++)
      triangle[r][c] = triangle[r - 1][c - 1] + triangle[r - 1][c]

  return triangle[rowIndex]
}
  • 时间复杂度：O(rowIndex2)，需要填充杨辉三角中的每个元素
  • 空间复杂度：O(rowIndex2)，需要存储完整的杨辉三角

解题思路同 118. 杨辉三角，先生成一个完整的杨辉三角，然后返回对应行的数据。

3. 🎯 s.2 - 动态规划 ​

js
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
  let row = []
  for (let i = 0; i <= rowIndex; i++) {
    row.push(1)
    for (let j = i - 1; j > 0; j--) {
      row[j] = row[j - 1] + row[j]
    }
  }
  return row
}
  • 时间复杂度：O(rowIndex2)，需要遍历 rowIndex 行，每行更新的元素数量逐渐增加
  • 空间复杂度：O(rowIndex)，使用一个长度为 rowIndex + 1 的数组

算法思路：

  • 使用一维数组滚动更新，每次循环在数组末尾添加 1，然后从后往前更新中间元素
  • 从后往前更新可以避免覆盖还需要使用的值
  • 每个元素等于上一行对应位置和前一位置元素的和

Discussions